package leetcode.code0558;

import leetcode.IDebug;

public class Solution implements IDebug {

	class Node {
		public boolean val;
		public boolean isLeaf;
		public Node topLeft;
		public Node topRight;
		public Node bottomLeft;
		public Node bottomRight;

		public Node() {
		}

		public Node(boolean _val, boolean _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
			val = _val;
			isLeaf = _isLeaf;
			topLeft = _topLeft;
			topRight = _topRight;
			bottomLeft = _bottomLeft;
			bottomRight = _bottomRight;
		}
	};

	public Node intersect(Node quadTree1, Node quadTree2) {
		Node ans = new Node();
		if (quadTree1.isLeaf && quadTree2.isLeaf) {
			ans.isLeaf = true;
			ans.val = quadTree1.val | quadTree2.val;
		} else if (!quadTree1.isLeaf && quadTree2.isLeaf) {
			ans = this.intersect1(quadTree1, quadTree2.val);
		} else if (quadTree1.isLeaf && !quadTree2.isLeaf) {
			ans = this.intersect1(quadTree2, quadTree1.val);
		} else {
			ans.topLeft = this.intersect(quadTree1.topLeft, quadTree2.topLeft);
			ans.topRight = this.intersect(quadTree1.topRight, quadTree2.topRight);
			ans.bottomLeft = this.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
			ans.bottomRight = this.intersect(quadTree1.bottomRight, quadTree2.bottomRight);
			//
			if (ans.topLeft.isLeaf && ans.topRight.isLeaf && ans.bottomLeft.isLeaf && ans.bottomRight.isLeaf &&  ans.topLeft.val == ans.topRight.val && ans.topRight.val == ans.bottomLeft.val
					&& ans.bottomLeft.val == ans.bottomRight.val) {
				// 如果当前网格的值相同（即，全为 0 或者全为 1），
				// 将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
				ans.isLeaf = true;
				ans.val = ans.topLeft.val;
				ans.topLeft = null;
				ans.topRight = null;
				ans.bottomLeft = null;
				ans.bottomRight = null;
			} else {
				ans.isLeaf = false;
			}
		}
		return ans;
	}

	private Node intersect1(Node quadTree1, boolean val) {
		Node node = new Node();
		node.isLeaf = false;
		node.topLeft = this.newNode(val);
		node.topRight = this.newNode(val);
		node.bottomLeft = this.newNode(val);
		node.bottomRight = this.newNode(val);
		return this.intersect(quadTree1, node);
	}

	private Node newNode(boolean val) {
		Node node = new Node();
		node.isLeaf = true;
		node.val = val;
		return node;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
